'''
https://leetcode.cn/problems/wildcard-matching/
'''
from functools import cache


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        @cache
        def f(i, j):
            if i == m:
                return j == n or (p[j] == '*' and f(m, j + 1))
            elif j == n:
                return False
            else:
                if p[j] == '*':
                    # i+1,j+1，可以被i+1,j然后i,j+1走到
                    return f(i, j + 1) or f(i + 1, j)
                else:
                    return (s[i] == p[j] or p[j] == '?') and f(i + 1, j + 1)

        return f(0, 0)

    def isMatch2(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[m][n] = True
        for j in range(n - 1, -1, -1):
            dp[m][j] = dp[m][j+1] and p[j] == '*'
        for i in range(m-1, -1, -1):
            for j in range(n - 1, -1, -1):
                if p[j] == '*':
                    dp[i][j] = dp[i][j + 1] or dp[i + 1][j]
                else:
                    dp[i][j] = (s[i] == p[j] or p[j] == '?') and dp[i + 1][j + 1]
        return dp[0][0]
